The present invention relates to synchronization of shift registers in apparatus on transmitting and on receiving sides.
Linear Feedback Shift Registers (LFSRs) are known and are applied in applications such as sequence generators, scramblers, coders, descramblers and decoders. An LFSR can be a binary LFSR wherein a shift register element can hold a binary symbol, the binary symbol being represented by a binary signal. An LFSR can be a non-binary LFSR, wherein a shift register element can hold a non-binary symbol; a non-binary symbol having one of n states with n>2. A single non-binary symbol can be represented by a signal. In one embodiment such a signal representing a non-binary symbol can be a single non-binary signal able to have one of n states. A non-binary symbol in another embodiment can be represented by a plurality of signals, for instance, by a plurality of binary signals. For instance, an 8-state symbol can be represented by a word of 3 bits, each bit being represented by a binary signal.
A binary or n-state LFSR can be in Fibonacci or in Galois configuration.
In many applications, including in scrambling and descrambling and in spread-spectrum modulation a sequence of n-state symbols with n≧2 and n>2, some knowledge is required about a phase or synchronization of a sequence that was transmitted from a transmitter in order to be detected or decoded at a receiver. In the instant application, an n-state sequence is assumed to be associated with an n-state LFSR. In some cases one wants to know how a phase or synchronization point of a received sequence relates to an initial state of a sequence generator. In other cases one would like to start generating in parallel to a received sequence a sequence that is synchronized with the received sequence.
In general one applies one or more transition matrices to determine a state of an LFSR compared to a known state or to initiate an LFSR. Such calculations can be quite extensive and time consuming. Accordingly, novel and improved methods and apparatus are required to determine a desired state of an n-state LFSR with n≧2 or n>2.
The inventor has described in earlier patent applications how after determining an error location in a codeword one can determine the correct symbol value without first determining an error magnitude. Also described in earlier patent applications is the up-and-down approach in determining intermediate coding states. These aspects are described in U.S. Provisional Patent Application No. 60/807,087, filed Jul. 12, 2006, and U.S. Provisional Patent Application No. 60/821,980 filed Aug. 10, 2006 which are both incorporated herein by reference in their entirety. U.S. patent application Ser. No. 11/739,189 filed Apr. 26, 2007 and U.S. patent application Ser. No. 11/743,893 filed May 3, 2007 and U.S. patent application Ser. No. 11/775,963 filed on Jul. 11, 2007 are also incorporated herein by reference in their entirety.